/**
 * 希尔排序
 * @param {Array} arr 
 */
var hillSort = function (arr) {
  let len = arr.length;
  for (let gap = parseInt(arr.length / 2); gap > 0; gap = parseInt(gap / 2)) {
    // console.log('out: ', gap)
    for (var i = gap; i < len; i++) {
      let temp = arr[i];
      // console.log("in：", temp)
      // 从前面开始做比较
      for (var j = i-gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j+gap] = arr[j];
        // console.log('内部循环中',j, arr)
      }
      arr[j+gap] = temp;
      // console.log(`第${gap}轮`, arr)
    }
  }
  console.log(arr)
  return arr
}

hillSort([8, 9, 1, 2,5,6,2,3,0])

function insertSort(array) {
  for (let i = 1; i < array.length; i++) {
    let item = array[i];
    for (let j = 0; j < i; j++) {
      let rj = array[j];
      // 插入到数组指定位置
      if (item < rj) {
        // 删除第i个元素
        array.splice(i, 1);
        // 在指定位置插入元素
        array.splice(j, 1, item, rj);
        break;
      }
    }
  }
  return array;
}